import collections
import copy

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        out = []
        l_stack = collections.deque()
        r_stack = collections.deque()
        n = len(s)
        for i in range(n):
            if s[i] == '(':
                l_stack.append(i)
            else:
                if s[i] == ')':
                    if l_stack:
                        l_stack.pop()
                    else:
                        r_stack.append(i)
        l_max = len(l_stack)
        r_max = len(r_stack)

        def check(p):
            l_count = 0
            for i in range(len(p)):
                if p[i] == '(':
                    l_count += 1
                else:
                    if p[i] == ')':
                        l_count -= 1
                        if l_count < 0:
                            return False
            return True
        if r_stack:
            r_index = collections.deque()
            for i in range(r_stack[-1] + 1):
                if s[i] == ')':
                    r_index.append(i)
            total_l = len(r_index)
            select_index = collections.deque()
            r_set = set()
            def pick_index(r_id, count):
                if count == r_max:
                    p = ''
                    for k in range(len(select_index)):
                        if k == 0:
                            p += s[: select_index[k]]
                        if k < len(select_index) - 1:
                            p += s[select_index[k] + 1: select_index[k + 1]]
                        else:
                            p += s[select_index[k] + 1:r_stack[-1] + 1]
                    if check(p):
                        r_set.add(p)
                else:
                    for j in range(r_id, total_l - (r_max - count) + 1):
                        select_index.append(r_index[j])
                        pick_index(j + 1, count + 1)
                        select_index.pop()
            pick_index(0, 0)
            out = list(r_set)
        if r_stack:
            if l_stack:
                base = s[r_stack[-1] + 1: l_stack[0]]
            else:
                base = s[r_stack[-1] + 1:]
        else:
            if l_stack:
                base = s[:l_stack[0]]
            else:
                base = s
        if not out:
            out = [base]
        else:
            for i in range(len(out)):
                out[i] = out[i] + base
        if l_stack:
            l_index = collections.deque()
            for i in range(l_stack[0], n):
                if s[i] == '(':
                    l_index.append(i)
            total_l = len(l_index)
            select_index = collections.deque()
            l_set = set()
            def pick_index(l_id, count):
                if count == l_max:
                    p = ''
                    for k in range(len(select_index)):
                        if k == 0:
                            p += s[l_stack[0]: select_index[k]]
                        if k < len(select_index) - 1:
                            p += s[select_index[k] + 1: select_index[k + 1]]
                        else:
                            p += s[select_index[k] + 1:]
                    if check(p):
                        l_set.add(p)
                else:
                    for j in range(l_id, total_l - (l_max - count) + 1):
                        select_index.append(l_index[j])
                        pick_index(j + 1, count + 1)
                        select_index.pop()
            pick_index(0, 0)
            out1 = copy.deepcopy(out)
            out = []
            for s1 in out1:
                for s2 in l_set:
                    out.append(s1 + s2)
        return out



data = Solution()
s = ')()('
print(data.removeInvalidParentheses(s))
s = '()())()'
print(data.removeInvalidParentheses(s))
s = '(a)())()'
print(data.removeInvalidParentheses(s))
s = ')('
print(data.removeInvalidParentheses(s))
s = "(r(()()("
print(data.removeInvalidParentheses(s))
s = "(()"
print(data.removeInvalidParentheses(s))
s = ")()))())))"
print(data.removeInvalidParentheses(s))